home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / thesauri / merge.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  26.8 KB  |  754 lines
  1. /*
  2.    PROGRAM NAME:  merge.c
  3.  
  4.    PURPOSE:  This program is used to merge two separate hierarchies.
  5.              The program first reads each inverted file.  It then reads in the
  6.              corresponding link file which gives parent-child links to build
  7.              the hierarchy.  It can then perform two different types of mergers:
  8.  
  9.              1) Simple merge in which a point of connection between the two 
  10.                 thesauri is made wherever they have terms in common.
  11.  
  12.              2) Complex merge in which any two terms are connected if they
  13.                 have sufficiently (above a specified threshold) similar
  14.                 sets of parent and child terms.
  15.  
  16.    INPUT FILES REQUIRED: 
  17.    
  18.              1)  inverted file for 1st hierarchy  
  19.  
  20.              2)  links file for 1st hierarchy
  21.  
  22.              3)  inverted file for 2nd hierarchy
  23.  
  24.              4)  links file for 2nd hierarchy
  25.  
  26.              An inverted file consists of sequences of
  27.        
  28.                  term       document number       weight
  29.  
  30.                  (multiple entries for any term should be grouped together)
  31.  
  32.              A link file consists of sequences of
  33.    
  34.                  parent term          child term
  35.  
  36.    PARAMETERS TO BE SET BY USER: 
  37.  
  38.              1) MAXWORD:  which specifies the maximum size of a term
  39.              2) THRESHOLD:  which specifies the minimum similarity level 
  40.                 for use in complex merge.
  41.  
  42.    COMMAND LINE:
  43.  
  44.      merge inverted_file_1 link_file_1 inverted_file_2 link_file_2 output_file
  45.  
  46. ****************************************************************************/
  47.  
  48. #include <stdio.h>
  49. #include <string.h>
  50. #include <math.h>
  51. #define MAXWORD 20              /* maximum size of a term                   */
  52. #define THRESHOLD 0.6           /* similarity threshold for complex_merge   */
  53.  
  54. struct doclist {                /* sequences of document # and weight       */
  55.   int doc;                      /* document number                          */
  56.   float weight;                 /* term weight in document                  */
  57.   struct doclist *nextdoc;      /* ptr. to next doclist record              */
  58. } doclistfile;
  59.  
  60. struct parentlist {             /* sequences of parent terms                */
  61.   char term[MAXWORD];           /* parent term                              */
  62.   struct invert *parent;        /* ptr. to parent term in inverted file     */
  63.   struct parentlist *nextparent;/* ptr. to next parentlist record           */
  64. } parentfile;
  65.  
  66. struct connections {            /* holds information about connected terms  */
  67.   struct invert *termadd;       /* address of connected term in inverted file */
  68.   struct connections *next_connection /* ptr. to next connections record    */
  69. } connectlist;
  70.  
  71. struct childlist {              /* sequences of child terms                 */
  72.   char term[MAXWORD];           /* child term                               */
  73.   struct invert *child;         /* ptr. to child term in inverted file      */
  74.   struct childlist *nextchild;  /* ptr. to next childlist record            */
  75. } childfile;
  76.  
  77. struct invert {                 /* inverted file                            */
  78.   char term[MAXWORD];           /* term                                     */
  79.   struct doclist *doc;          /* sequences of document # and weight       */
  80.   struct parentlist *parents;   /* pointer to list of parent terms          */
  81.   struct childlist *children;   /* pointer to list of children terms        */
  82.   struct connections *connect;    /* pointer to connection in other hierarchy */
  83.   struct invert *nextterm;      /* ptr. to next invert record               */
  84. } invfile;
  85.  
  86. static struct invert *startinv;        /* ptr. to first record in inverted file    */
  87. static struct invert *lastinv;         /* ptr. to last record in inverted file     */ 
  88. static struct doclist *lastdoc;        /* ptr. to last document in doclist         */
  89. static struct invert *start_inv1;      /* ptr. to the start of 1st inverted file   */
  90. static struct invert *start_inv2;      /* ptr. to the start of 2nd inverted file   */
  91.  
  92. static FILE *input1;                   /* first inverted file                      */
  93. static FILE *input2;                   /* first link file                          */
  94. static FILE *input3;                   /* second inverted file                     */
  95. static FILE *input4;                   /* second link file                         */
  96. static FILE *output;                   /* holds any outputs                        */
  97.  
  98. static char currentterm[MAXWORD];      /* tracks current term in inverted file     */
  99.  
  100. static struct invert *get_mem_invert();        /* these four get_mem functions     */
  101. static struct doclist *get_mem_doclist();      /* obtain memory dynamically for    */
  102. static struct parentlist *get_mem_parentlist();/* storing different types of       */
  103. static struct childlist *get_mem_childlist();  /* records.                         */
  104. static struct connections *get_mem_connections();
  105.  
  106. static struct invert *find_term();       /* searches for term in inverted file and */
  107.                                          /* returns address of the term            */
  108. static int compare();
  109.   
  110. static
  111. void initialize(),                      /* initialize global variables          */
  112.      open_files(),                      /* open files                           */
  113.      read_invfile(),                    /* read in the inverted file            */
  114.      add_invert(),                      /* called within read_invfile()         */
  115.      read_links(),                      /* read in the links information        */
  116.      add_link(),                        /* called within read_links()           */
  117.      pr_invert(),                       /* print the inverted file              */
  118.      simple_merge(),                    /* simple merge between both hierarchies*/
  119.      complex_merge();                   /* complex merge between hierarchies    */
  120.  
  121. int main(argc,argv)
  122. int argc;
  123. char *argv[];
  124. {
  125.  
  126. char ch;
  127.  
  128. if (argc!=6)
  129.   {
  130.   (void) printf("There is an error in the command line\n");
  131.   (void) printf("Correct usage is:\n");
  132.   (void) printf("merge inverted_file_1 link_file_1 inverted_file_2 link_file_2 output_file\n");
  133.   exit(1);
  134.   }
  135.  
  136. start_inv1 = NULL; start_inv2 = NULL; /* initialize start of both inverted files */
  137.   
  138. initialize();
  139. open_files(argv);
  140. (void) fprintf(output,"\nREADING FIRST INVERTED FILE\n");
  141. read_invfile(input1);
  142. start_inv1 = startinv;
  143. (void) fprintf(output,"\nREADING FIRST LINK FILE\n");
  144. read_links(input2,start_inv1); 
  145. (void) fprintf(output,"\nPRINTING FIRST INVERTED FILE\n\n");
  146. pr_invert(start_inv1);
  147. /* re-initialize */
  148. initialize();
  149. (void) fprintf(output,"\nREADING SECOND INVERTED FILE\n");
  150. read_invfile(input3);
  151. start_inv2 = startinv;
  152. (void) fprintf(output,"\nREADING SECOND LINK FILE\n");
  153. read_links(input4,start_inv2);
  154. (void) fprintf(output,"\nPRINTING SECOND INVERTED FILE\n\n");
  155. pr_invert(start_inv2);
  156.  
  157. (void) printf("Make a selection\n");
  158. (void) printf("To use the simple_merge algorithm, enter 1\n");
  159. (void) printf("To use the complex_merge algorithm, enter 2\n");
  160. (void) printf("\nEnter selection: ");
  161.  
  162. ch = getchar();
  163.  
  164. switch(ch)
  165.   {
  166.   case '1':
  167.       (void) fprintf(output,"\nPERFORMING A SIMPLE MERGE OF THE TWO INVERTED FILES\n");
  168.       simple_merge(start_inv1,start_inv2); 
  169.       (void) fprintf(output,"\nPRINTING FIRST INVERTED FILE AFTER SIMPLE MERGE\n\n");
  170.       pr_invert(start_inv1);
  171.       (void) fprintf(output,"\nPRINTING SECOND INVERTED FILE AFTER SIMPLE MERGE\n\n");
  172.       pr_invert(start_inv2);
  173.       break;
  174.   case '2':
  175.       (void) fprintf(output,"\nPERFORMING A COMPLEX MERGE OF THE TWO INVERTED FILES\n");
  176.       complex_merge(start_inv1,start_inv2);
  177.       (void) fprintf(output,"\nPRINTING FIRST INVERTED FILE AFTER COMPLEX MERGE\n\n");
  178.       pr_invert(start_inv1);
  179.       (void) fprintf(output,"\nPRINTING SECOND INVERTED FILE AFTER COMPLEX MERGE\n\n");
  180.       pr_invert(start_inv2);
  181.   }
  182.  
  183. (void) fclose(input1);(void) fclose(input2);
  184. (void) fclose(input3);(void) fclose(input4);(void) fclose(output);
  185.  
  186. return(0);
  187.  
  188. }
  189.  
  190. /***************************************************************************
  191.  
  192.      open_files(argv)
  193.  
  194.      Returns:  void
  195.  
  196.      Purpose:  Open all input & output files 
  197.  
  198. **/
  199.  
  200. static void open_files(argv)
  201. char *argv[];
  202. {
  203. if (( input1 = fopen(argv[1],"r")) == NULL ) {
  204.    (void) printf("couldn't open file %s\n",argv[1]);
  205.    exit(1); /* inverted file for first thesaurus hierarchy  */ 
  206. }
  207.  
  208. if (( input2 = fopen(argv[2],"r")) == NULL ) {
  209.    (void) printf("couldn't open file %s\n",argv[2]);
  210.    exit(1); /* link file for first thesaurus hierarchy */
  211. }
  212.  
  213. if (( input3 = fopen(argv[3],"r")) == NULL ) {
  214.    (void) printf("couldn't open file %s\n",argv[3]);
  215.    exit(1); /* inverted file for second thesaurus hierarchy  */ 
  216. }
  217.  
  218. if (( input4 = fopen(argv[4],"r")) == NULL ) {
  219.    (void) printf("couldn't open file %s\n",argv[4]);
  220.    exit(1); /* link file for second thesaurus hierarchy */
  221. }
  222.  
  223. if (( output = fopen(argv[5],"w")) == NULL) {
  224.    (void) printf("couldn't open file %s for output \n",argv[5]);
  225.    exit(1); /* output file */
  226. }
  227.  
  228. }
  229.  
  230. /***************************************************************************
  231.  
  232.      initialize()
  233.  
  234.      Returns:  void
  235.  
  236.      Purpose:  Initialize global variables 
  237.  
  238. **/
  239.  
  240. static void initialize()
  241. {
  242. startinv = NULL;             /* start of inverted file        */
  243. lastinv = NULL;              /* end of inverted file          */
  244. lastdoc = NULL;              /* last document considered      */
  245. currentterm[0] = '\0';       /* current term being considered */
  246.  
  247. }
  248.  
  249. /***************************************************************************
  250.  
  251.      read_invfile(input)
  252.  
  253.      Returns:  void
  254.  
  255.      Purpose:  Read the inverted file from a disk file 
  256.  
  257. **/
  258.  
  259. static void read_invfile(input)
  260. FILE *input;
  261. {
  262. int docid;                    /* holds current document number                 */
  263. char temp[MAXWORD];           /* holds current term                            */
  264. float weight;                 /* holds current term weight                     */
  265. struct doclist *p;            /* structure to hold document numner-weight pair */
  266.  
  267. (void) fscanf(input,"%s%d%f",temp,&docid,&weight);    /* read next line        */
  268. while (strlen(temp) > 0)                       /* while a legitimate line      */
  269. {
  270. if (!strncmp(currentterm,temp,MAXWORD)) { 
  271. /* if temp is the same as current term then simply add next document-weight info*/
  272.    p = get_mem_doclist();              
  273.    p->doc = docid;             /* assign doc. number  */
  274.    p->weight = weight;         /* assign doc. weight  */
  275.    p->nextdoc = NULL;
  276.    if (lastdoc) lastdoc->nextdoc = p; /* connect p to doclist chain for this term */
  277.    lastdoc = p;                /* set this global variable   */
  278. }
  279. else add_invert(docid,temp,weight); /* temp not the same as current term, hence */
  280. temp[0] = '\0';                     /* start a new entry in the inverted file   */
  281. (void) fscanf(input,"%s%d%f",temp,&docid,&weight);      /* read next input line */
  282. }
  283. }
  284.  
  285. /***************************************************************************
  286.  
  287.      add_invert(docid,temp,weight)
  288.  
  289.      Returns:  void
  290.  
  291.      Purpose:  Called in read_invfile when a new term is being read from the file.
  292.                Starts a new entry in the inverted file.
  293.  
  294. **/
  295.  
  296. static void add_invert(docid,temp,weight)
  297. int docid;                          /* in: document number                      */
  298. char temp[MAXWORD];                 /* in: new index term                       */
  299. float weight;                       /* in: index term weight                    */
  300. {
  301. struct invert *p;                   /* structure p will be attached to inv. file  */
  302.  
  303. p = get_mem_invert();               /* get memory for p                         */
  304. (void) strncpy(p->term,temp,MAXWORD);      /* copy over the term                */
  305. p->parents = NULL;                  /* initially term has no parents            */
  306. p->children = NULL;                 /* also no children terms                   */
  307. p->doc = get_mem_doclist();         /* get memory for a doclist structure       */
  308. p->doc->doc = docid;                /* assign the document number               */
  309. p->doc->weight = weight;            /* assign term weight                       */
  310. p->doc->nextdoc = NULL;
  311. p->connect = NULL;                  /* initially this term not connected to any */
  312.                                     /* other in any other hierarchy             */
  313. p->nextterm = NULL;
  314. if (startinv == NULL) startinv = p; /* if this is the 1st term in inverted file */
  315. if (lastinv) lastinv->nextterm = p; /* always update lastinv pointer            */
  316. lastinv = p;
  317. lastdoc = p->doc;
  318. (void) strncpy(currentterm,temp,MAXWORD);  /* update the value of currentterm to the   */
  319.                                     /* new term that has just been read         */
  320. }
  321.  
  322. /***************************************************************************
  323.   
  324.      read_links(input,startinv)
  325.  
  326.      Returns:  void
  327.  
  328.      Purpose:  Add the link information to the inverted file
  329.  
  330. **/
  331.  
  332. static void read_links(input,startinv)
  333. FILE *input;                          /* in:  input file                  */
  334. struct invert *startinv;              /* in: start of this inverted file  */
  335. {
  336. char parent[MAXWORD],                 /* holds parent term                */
  337.      child[MAXWORD];                  /* holds child term                 */
  338.  
  339. (void) fscanf(input,"%s%s",parent,child);    /* read first input line     */
  340. while (strlen(parent) > 0 && strlen(child) > 0) /* while non-trivial input    */
  341. {
  342. if (!find_term(parent,startinv) || !find_term(child,startinv))
  343.    {
  344.    (void) printf("Please check your input files\n");
  345.    (void) printf("Term %s or term %s is not in inverted file\n",parent,child);
  346.    exit(0);
  347.    }
  348. add_link(parent,child,startinv);      /* this function makes links        */
  349. child[0] = '\0'; parent[0] = '\0';    /* throw out old parent & child info*/
  350. (void) fscanf(input,"%s%s",parent,child);    /* read next line            */
  351. }
  352. }
  353.  
  354. /***************************************************************************
  355.  
  356.      add_link(parent,chile,startinv)
  357.  
  358.      Returns:  void
  359.  
  360.      Purpose:  Function is used within read_links 
  361.  
  362. **/
  363.  
  364. static void add_link(parent,child,startinv)
  365. char    parent[MAXWORD],       /* in:  specify parent term                */
  366.         child[MAXWORD];        /* in:  specify child term                 */
  367. struct invert *startinv;       /* in:  specify start of this inv. file    */
  368. {
  369. struct invert *p, *q;          /* holds adds. of both terms in inv. file  */
  370. struct parentlist *new_parent; /* structure to hold new parent info.      */
  371. struct childlist *new_child;   /* structure to hold new child info.       */
  372.  
  373. p = find_term(parent, startinv);         /* find address of parent & child*/
  374. q = find_term(child, startinv);          /* terms in the inverted file    */
  375.  
  376. /* first add parent links for the given child  */
  377.  
  378. new_parent = get_mem_parentlist();       /* get memory for parent record  */
  379. (void) strncpy(new_parent->term,parent,MAXWORD);      /* copy over parent term   */
  380. new_parent->parent = p;   /* store addr. (in inverted file) of parent term*/
  381. if (q->parents == NULL) {    /* i.e. no parents listed for this child yet */
  382.    q->parents = new_parent;                 /* first parent link made     */
  383.    new_parent->nextparent = NULL;
  384. }
  385. else {                /* at least 1 parent already listed for given child */
  386.    new_parent->nextparent = q->parents; /* attach new parent in front of list */
  387.    q->parents = new_parent;
  388. }
  389.  
  390. /* next add child links for given parent   */
  391.  
  392. new_child = get_mem_childlist();        /* get memory for child record     */
  393. (void) strncpy(new_child->term,child,MAXWORD);       /* copy over child term      */
  394. new_child->child = q;      /* store addr. (in inverted file) of child term */
  395. if (p->children == NULL) {    /* i.e. no child terms listed for this parent*/
  396.    p->children = new_child;                   /* first child link made     */
  397.    new_child->nextchild = NULL;
  398. }
  399. else {                 /* at least 1 child already exists for given parent */
  400.    new_child->nextchild = p->children;/* attach new child to front of list */
  401.    p->children = new_child;
  402. }
  403. }
  404.  
  405. /***************************************************************************
  406.  
  407.      pr_invert(startinv)
  408.  
  409.      Returns:  void
  410.  
  411.      Purpose:  Print either inverted file.  Prints each term, its
  412.                associated document numbers, term-weights and parent
  413.                and child terms.
  414.  
  415. **/
  416.  
  417. static void pr_invert(startinv)
  418. struct invert *startinv;            /* in: specifies start of inverted file    */
  419. {
  420. struct invert *inv_addr;            /* tracks add. of current inv. file record */
  421. struct doclist *doc_addr;           /* tracks add. of current doclist record   */
  422. struct parentlist *parent_addr;     /* tracks add. of current parentlist record*/
  423. struct childlist *child_addr;       /* tracks add. of current childlist record */
  424. struct connections *connect_term_add; /* tracks connected terms                 */
  425.  
  426. inv_addr = startinv;                         /* begin at top of inv. file      */
  427. while (inv_addr) {                           /* while a legitimate term....    */
  428.   (void) fprintf(output,"TERM: %s\nPARENT TERMS: ",inv_addr->term);
  429.   parent_addr = inv_addr->parents;           /* find addr. of first parent     */
  430.   while (parent_addr) {                      /* printing all parents           */
  431.      (void) fprintf(output,"%s",parent_addr->term);
  432.      parent_addr = parent_addr->nextparent;  /* loop through remaining parents */
  433.      if(parent_addr) (void) fprintf(output,", ");
  434.   }
  435.   (void) fprintf(output,"\nCHILD TERMS: ");
  436.   child_addr = inv_addr->children;           /* find addr. of first child      */
  437.   while (child_addr) {                       /* printing all children          */
  438.      (void) fprintf(output,"%s",child_addr->term);
  439.      child_addr = child_addr->nextchild;     /* loop through remaining childrend */
  440.      if(child_addr) (void) fprintf(output,", ");
  441.   }
  442.   (void) fprintf(output,"\nDOCUMENT NUMBER                TERM WEIGHT\n");
  443.   doc_addr = inv_addr->doc;               /* find addr. of first associated doc. */
  444.   while (doc_addr) {                         /* printing all documents         */
  445.      (void) fprintf(output,"%-30d ",doc_addr->doc);
  446.      (void) fprintf(output,"%-10.5f\n",doc_addr->weight);
  447.      doc_addr = doc_addr->nextdoc;           /* loop through remaining docs.    */
  448.   }
  449. /* if the terms is connected then print the term from the other hierarchy */
  450.   (void) fprintf(output,"CONNECTIONS IN OTHER THESAURUS HIERARCHY:\n");
  451.   connect_term_add = inv_addr->connect;
  452.   while (connect_term_add) 
  453.     {
  454.     (void) fprintf(output,"     %s",connect_term_add->termadd->term);
  455.     connect_term_add = connect_term_add->next_connection;
  456.     if(connect_term_add) (void) fprintf(output,", ");
  457.     }
  458.   (void) fprintf(output,"\n\n");
  459.   inv_addr = inv_addr->nextterm;            /* loop to next term in inverted file */
  460. }
  461. }
  462.  
  463. /***************************************************************************
  464.  
  465.      simple_merge(startinv1,startinv2)
  466.  
  467.      Returns:  void
  468.  
  469.      Purpose:  In this function, two terms in different hierarchies are merged
  470.                if they are identical.  
  471.  
  472. **/
  473.  
  474. static void simple_merge(startinv1, startinv2)
  475. struct invert *startinv1,          /* in:  specifies start of 1st inv. file  */
  476.               *startinv2;          /* in:  specifies start of 2nd inv. file  */
  477. {
  478. struct invert *inv_addr1, *inv_addr2;
  479. struct connections *r1, *r2;  /* storage to hold info. about connected terms  */
  480.  
  481. inv_addr1 = startinv1;              /* start with top of 1st inv. file        */
  482. while(inv_addr1) {          /* looking for this term in the other inv. file   */
  483.   inv_addr2 = find_term(inv_addr1->term, startinv2);
  484.   if (inv_addr2) {                   /* if term was found then update connect */
  485.     r1 = get_mem_connections();
  486.     r1->termadd = inv_addr2;
  487.     r1->next_connection = inv_addr1->connect;
  488.     inv_addr1->connect = r1;
  489.     r2 = get_mem_connections();
  490.     r2->termadd = inv_addr1;
  491.     r2->next_connection = inv_addr2->connect;
  492.     inv_addr2->connect = r2;
  493.   }
  494.   inv_addr1 = inv_addr1->nextterm;
  495. }
  496. }
  497.  
  498. /***************************************************************************
  499.  
  500.      complex_merge(startinv1,startinv2)
  501.  
  502.      Returns:  void
  503.  
  504.      Purpose:  In this routine any two terms in different hierarchies are merged
  505.                if they have 'similar' parents and children.  Similarity is
  506.                computed and compared to a pre-fixed user specified THRESHOLD 
  507.  
  508. **/
  509.  
  510. static void complex_merge(startinv1, startinv2)
  511. struct invert *startinv1,         /* in: specifies start of 1st inv. file  */
  512.               *startinv2;         /* in: specifies start of 2nd inv. file  */
  513. {
  514. struct invert *inv1_addr,         /* tracks current term in 1st inv. file  */
  515.               *inv2_addr;         /* tracks current term in 2nd inv. file  */
  516. struct connections *r1, *r2;      /* tracks connected terms                */
  517. int compare();
  518.  
  519. inv1_addr = startinv1;            /* begin at top of 1st inv. file         */
  520. while(inv1_addr) {                /* while addr. legitimate ....           */
  521.    inv2_addr = startinv2;         /* now begin at top of 2nd inv. file     */
  522.    while(inv2_addr) {
  523.      if (compare(inv1_addr,inv2_addr)) {   /* this returns 1 of 2 terms are */
  524.                             /* similar enough, then connect the two terms   */
  525.        r1 = get_mem_connections();
  526.        r1->termadd = inv2_addr;
  527.        r1->next_connection = inv1_addr->connect;
  528.        inv1_addr->connect = r1;
  529.        r2 = get_mem_connections();
  530.        r2->termadd = inv1_addr;
  531.        r2->next_connection = inv2_addr->connect;
  532.        inv2_addr->connect = r2;
  533.      }
  534.      inv2_addr = inv2_addr->nextterm;    /* loop through 2nd inv. file     */
  535.    } 
  536. inv1_addr = inv1_addr->nextterm;         /* loop through 1st inv. file     */
  537. }
  538. }
  539.  
  540. /***************************************************************************
  541.  
  542.      compare(p,q)
  543.  
  544.      Returns:  int
  545.  
  546.      Purpose:  Used to compare two terms for more than just equality.
  547.                A similarity value is computed and if it is greater than a 
  548.                THRESHOLD then 1 is returned, else 0 
  549.  
  550. **/
  551.  
  552. static int compare(p,q)
  553. struct invert *p, *q;     /* addresses of two terms to be compared       */
  554. {
  555. struct parentlist *parent1,  /* tracks parentlist of 1st term   */
  556.                   *parent2;  /* tracks parentlist of 2nd term   */
  557. struct childlist  *child1,   /* tracks childlist of 1st term    */
  558.                   *child2;   /* trakcs childlist of 2nd term    */
  559. float count1,                /* tracks # of parents + children of 1st term */
  560.       count2,                /* tracks # of parents + children of 2nd term */ 
  561.       count;                 /* tracks # of common parents + children      */
  562.  
  563. count = 0.0; count1 = 0.0; count2 = 0.0;  /* initialize all counts         */
  564.  
  565. /* first check # of parents for p->term & the # of common parents */
  566.  
  567. parent1 = p->parents;
  568. while(parent1) {    /* parent of 1st term */
  569.   count1 = count1 + 1.0;
  570.   parent2 = q->parents;
  571.   while(parent2) {        /* loop through parents of second term   */
  572.     if(!strncmp(parent1->term,parent2->term,MAXWORD)) count = count + 1.0;
  573.     parent2 = parent2->nextparent;
  574.   }
  575. parent1 = parent1->nextparent;
  576. }
  577.  
  578. /* next compute # of parents for q->term */
  579.  
  580. parent2 = q->parents;
  581. while (parent2) {   /* loop through parents of 2nd term again */
  582.   count2 = count2 + 1.0;
  583.   parent2 = parent2->nextparent;
  584. }
  585.  
  586. /* now check # of children for p->term & the # of common children */
  587.  
  588. child1 = p->children;
  589. while(child1) {   /* loop through children of 1st term     */
  590.   count1 = count1 + 1.0;
  591.   child2 = q->children;
  592.   while(child2) {   /* loop through children of 2nd term     */
  593.     if (!strncmp(child1->term,child2->term,MAXWORD)) count = count + 1.0;
  594.     child2 = child2->nextchild;
  595.   }
  596. child1 = child1->nextchild;
  597. }
  598.  
  599. /* next compute # of children for q->term */
  600.  
  601. child2 = q->children;
  602. while (child2) {     /* loop through children of 2nd term   */
  603.   count2 = count2 + 1.0;
  604.   child2 = child2->nextchild;
  605. }
  606.  
  607. if (count != 0.0) { /* if there is anything in common at all */
  608.   if ((count/(sqrt(count1 * count2))) >= THRESHOLD) {
  609.      /* printf("value is %f\n",(count/(sqrt(count1*count2)))); */
  610.      return(1);
  611.   }
  612.   else return(0);
  613. }
  614. return(0);
  615. }
  616.  
  617. /***************************************************************************
  618.  
  619.      find_term(term,startinv)
  620.  
  621.      Returns:  address of a struct invert record
  622.  
  623.      Purpose:  Search for a specified term in the specified inverted file
  624.                and return address of the corresponding record.  If not
  625.                found then returns NULL.
  626.  
  627. **/
  628.  
  629. static struct invert *find_term(term, startinv)
  630. char term[MAXWORD];       /*  in: term to be searched         */
  631. struct invert *startinv;  /*  in:  inverted file to search in */
  632. {
  633. struct invert *inv_addr;
  634.  
  635. inv_addr = startinv;      /* begin at top of inverted file    */
  636. while(inv_addr) {
  637.   if (!strcmp(term,inv_addr->term)) return(inv_addr);
  638.   inv_addr = inv_addr->nextterm;
  639. }
  640. return(NULL);
  641. }
  642.  
  643. /***************************************************************************
  644.  
  645.      *get_mem_invert()
  646.  
  647.      Returns:  address of a struct invert record
  648.  
  649.      Purpose:  dynamically obtain enough memory to store 1 invert record
  650.  
  651. **/
  652.  
  653. static struct invert *get_mem_invert()
  654. {
  655. struct invert *record;
  656.  
  657. record = (struct invert *)malloc(sizeof(invfile));
  658. if (!record) {
  659.     (void) fprintf(output,"\nout of memory\n");
  660.     return(NULL);
  661. }
  662. return(record);
  663. }
  664.  
  665. /***************************************************************************
  666.  
  667.      *get_mem_doclist()
  668.  
  669.      Returns:  address of a struct doclist record
  670.  
  671.      Purpose:  dynamically obtain enough memory to store 1 doclist record
  672.  
  673. **/
  674.  
  675. static struct doclist *get_mem_doclist()
  676. {
  677. struct doclist *record;
  678.  
  679. record = (struct doclist *)malloc(sizeof(doclistfile));
  680. if (!record) {
  681.     (void) fprintf(output,"\nout of memory\n");
  682.     return(NULL);
  683. }
  684. return(record);
  685. }
  686.  
  687. /***************************************************************************
  688.  
  689.      *get_mem_parentlist()
  690.  
  691.      Returns:  address of a struct parentlist record
  692.  
  693.      Purpose:  dynamically obtain enough memory to store 1 parentlist record.
  694.  
  695. **/
  696.  
  697. static struct parentlist *get_mem_parentlist()
  698. {
  699. struct parentlist *record;
  700.  
  701. record = (struct parentlist *)malloc(sizeof(parentfile));
  702. if (!record) {
  703.     (void) fprintf(output,"\nout of memory\n");
  704.     return(NULL);
  705. }
  706. return(record);
  707. }
  708.  
  709. /***************************************************************************
  710.  
  711.      *get_mem_childlst()
  712.  
  713.      Returns:  address of a struct childlist record
  714.  
  715.      Purpose:  dynamically obtain enough memory to store 1 childlist record.
  716.  
  717. **/
  718.  
  719. static struct childlist *get_mem_childlist()
  720. {
  721. struct childlist *record;
  722.  
  723. record = (struct childlist *)malloc(sizeof(childfile));
  724. if (!record) {
  725.     (void) fprintf(output,"\nout of memory\n");
  726.     return(NULL);
  727. }
  728. return(record);
  729. }
  730.  
  731.  
  732. /***************************************************************************
  733.  
  734.      *get_mem_connections()
  735.  
  736.      Returns:  address of a struct connections record
  737.  
  738.      Purpose:  dynamically obtain enough memory to store 1 connections record.
  739.  
  740. **/
  741.  
  742. static struct connections *get_mem_connections()
  743. {
  744. struct connections *record;
  745.  
  746. record = (struct connections *)malloc(sizeof(connectlist));
  747. if (!record) {
  748.     (void) fprintf(output,"\nout of memory\n");
  749.     return(NULL);
  750. }
  751. return(record);
  752. }
  753.  
  754.